package leetcode.nnumsum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lc15 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int first = 0; first < nums.length - 2; first++) {
            if (first != 0 && nums[first] == nums[first - 1]) continue;
            int l = first + 1;
            int r = nums.length - 1;
            int target = -nums[first];
            while (l < r) {
                if (nums[l] + nums[r] == target) {
                    ArrayList<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[first]);
                    tmp.add(nums[l]);
                    tmp.add(nums[r]);
                    ans.add(tmp);
                    int numLeft = nums[l];
                    while (l < r && nums[l] == numLeft) l++;
                    int numRight = nums[r];
                    while (l < r && nums[r] == numRight) r--;
                } else if (nums[l] + nums[r] < target) {
                    l++;
                } else r--;
            }
        }
        return ans;
    }


}
